//
// Created by lanlu on 2025/8/13.
//

// 弗洛伊德算法
#include <iomanip>
#include <vector>
#include <iostream>
using namespace std;

// 无穷大 使用int最大值初2 避免加法溢出
// 标准写法
const int INF = INT_MAX / 2;

void floyd(vector<vector<int> > &graph)
{
    int n = graph.size();

    // 从第一个顶点开始，看作是中间顶点，通过中间顶点来连接起始顶点和目标顶点
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++) // 起点
        {
            for (int j = 0; j < n; j++) // 目标
            {
                // k = 1, i = 0, j = 2时  将 [0][1] + [1][2] = [0][2]
                if (graph[i][k] != INF && graph[k][j] != INF)
                {
                    graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j]);
                }
            }
        }
    }
}

void printVector(vector<vector<int> > v)
{
    for (vector<int> v1: v)
    {
        for (int i: v1)
        {
            if (i == INF)
            {
                cout << "INF  ";
                continue;
            }
            // setw函数 设置输出宽度为3
            cout << setw(3) << i << "  ";
        }
        cout << endl;
    }
}

int main()
{
    // 声明有7个顶点 顶点的名字 0123456
    int n = 7;
    // 使用二维数组来表示边 创建n*n的二维数组 并且设置初始值为INF
    vector<vector<int> > graph(n, vector<int>(n, INF));
    // 添加边
    graph[0][1] = 6; // 0 -> 1 权重是6
    graph[0][3] = 2; // 0 -> 3 权重是2
    graph[1][2] = 5;
    graph[1][5] = 3;
    graph[3][1] = 7;
    graph[3][4] = 5;
    graph[4][5] = 5;
    graph[4][6] = 1;
    graph[5][2] = 3;

    printVector(graph);
    floyd(graph);
    cout << "-----after floyd:" << endl;
    printVector(graph);

    return 0;
}
